<html>
<head>
  <title>DSASolution</title>
  <basefont face="微软雅黑" size="2" />
  <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
  <meta name="exporter-version" content="Evernote Windows/307027 (zh-CN, DDL); Windows/6.1.0 (Win32);"/>
  <style>
    body, td {
      font-family: 微软雅黑;
      font-size: 10pt;
    }
  </style>
</head>
<body>
<a name="669"/>
<h1>DSASolution</h1>

<div>
<span><div><div><h1><span>Binary Search - 二分查找</span></h1><h2><span>题解</span></h2><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">对于已排序升序(升序)数组，使用二分查找可满足复杂度要求，注意数组中可能有重复值，所以需要使用类似</span><span style="-en-paragraph: true;">lower_bound</span><span style="-en-paragraph: true;">中提到的方法。</span></div><h3>Java</h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class Solution {</div><div>    /**</div><div>     * @param nums: The integer array.</div><div>     * @param target: Target to find.</div><div>     * @return: The first position of target. Position starts from 0.</div><div>     */</div><div>    public int binarySearch(int[] nums, int target) {</div><div>        if (nums == null || nums.length == 0) {</div><div>            return -1;</div><div>        }</div><div><br/></div><div>        int start = -1, end = nums.length;</div><div>        int mid;</div><div>        while (start + 1 &lt; end) {</div><div>            // avoid overflow when (end + start)</div><div>            mid = start + (end - start) / 2;</div><div>            if (nums[mid] &lt; target) {</div><div>                start = mid;</div><div>            } else {</div><div>                end = mid;</div><div>            }</div><div>        }</div><div><br/></div><div>        if (end == nums.length || nums[end] != target) {</div><div>            return -1;</div><div>        } else {</div><div>            return end;</div><div>        }</div><div>    }</div><div>}</div></div><h3>源码分析</h3><ol><li>首先对输入做异常处理，数组为空或者长度为0。</li><li>初始化 start, end, mid三个变量，这里start初始化为-1主要是考虑到end为1。注意mid的求值方法，可以防止两个整型值相加时溢出。</li><li><span style="font-weight: bold;">使用迭代而不是递归</span>进行二分查找，因为工程中递归写法存在潜在溢出的可能。</li><li>while终止条件应为start + 1 &lt; end而不是start &lt;= end，start == end时可能出现死循环。<span style="font-weight: bold;">即循环终止条件是相邻或相交元素时退出。</span>由于这里初始化时start &lt; end，所以一定是start + 1 == end时退出循环。</li><li>迭代终止时有两种情况，一种是在原数组中找到了，这种情况下一定是end, 因为start的更新只在nums[mid] &lt; target.</li><li>最后判断end和target的关系，先排除end为数组长度这种会引起越界的情况，然后再判断和目标值是否相等。</li></ol><h3>复杂度分析</h3><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">时间复杂度</span> <span style="-en-paragraph: true;">O(logn)O(\log n)</span><span style="-en-paragraph: true;">O</span><span style="-en-paragraph: true;">(</span><span style="-en-paragraph: true;">lo</span><span style="-en-paragraph: true;">g</span><span style="-en-paragraph: true;">n</span><span style="-en-paragraph: true;">)</span><span style="-en-paragraph: true;">, 空间复杂度</span> <span style="-en-paragraph: true;">(1)(1)</span><span style="-en-paragraph: true;">(</span><span style="-en-paragraph: true;">1</span><span style="-en-paragraph: true;">)</span><span style="-en-paragraph: true;">.</span></div><div>对于题中的 follow up, Java 中数组<b><font style="color: rgb(173, 0, 0);">不允许使用 long 型，</font></b>如果使用 long 型，那么数组大小可大 17GB 之巨！！几乎没法用。</div><div><br/></div><div><br/></div><div><br/></div><h1>Search Insert Position</h1><div><br/></div><h3>Problem Statement</h3><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">Given a sorted array and a target value, return the index if the target is</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">found. If not, return the index where it would be if it were inserted in</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">order.</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">You may assume</span> <span style="-en-paragraph: true; font-weight: bold;">NO</span> <span style="-en-paragraph: true;">duplicates in the array.</span></div><h4>Example</h4><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">[1,3,5,6]</span><span style="-en-paragraph: true;">, 5 → 2</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">[1,3,5,6]</span><span style="-en-paragraph: true;">, 2 → 1</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">[1,3,5,6]</span><span style="-en-paragraph: true;">, 7 → 4</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">[1,3,5,6]</span><span style="-en-paragraph: true;">, 0 → 0</span></div><h4>Challenge</h4><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">O(log(n)) time</span></div><h2>题解</h2><h3>Python</h3><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">问题可以转化为， 寻找</span><span style="-en-paragraph: true;">first position that value is &gt;= target</span><span style="-en-paragraph: true;">。如果没找到， 那么就插入在list的尾部。</span></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class Solution:</div><div>    &quot;&quot;&quot;</div><div>    @param A : a list of integers</div><div>    @param target : an integer to be inserted</div><div>    @return : an integer</div><div>    &quot;&quot;&quot;</div><div>    def searchInsert(self, A, target):</div><div>        if not A:</div><div>            return 0</div><div>        st, ed = 0, len(A) - 1</div><div>        while st + 1 &lt; ed:</div><div>            mid = (st + ed) / 2</div><div>            if A[mid] == target:</div><div>                ed = mid</div><div>            elif A[mid] &lt; target:</div><div>                st = mid</div><div>            else:</div><div>                ed = mid</div><div>        if A[st] &gt;= target:</div><div>            return st</div><div>        elif A[ed] &gt;= target:</div><div>            return ed</div><div>        else:</div><div>            return len(A)</div></div><h3>源码分析</h3><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">分析三种典型情况：</span></div><ol><li>目标值在数组范围之内，最后返回值一定是start + 1</li><li>目标值比数组最小值还小，此时start 一直为-1, 故最后返回start + 1 也没错，也可以将-1 理解为数组前一个更小的值</li><li>目标值大于等于数组最后一个值，由于循环退出条件为start + 1 == end, 那么循环退出时一定有start = A.length - 1, 应该返回start + 1</li></ol><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">综上所述，返回</span><span style="-en-paragraph: true;">start + 1</span><span style="-en-paragraph: true;">是非常优雅的实现。其实以上三种情况都可以统一为一种方式来理解，即索引</span><span style="-en-paragraph: true;">-1</span> <span style="-en-paragraph: true;">对应于在数组前方插入一个非常小的数，索引</span><span style="-en-paragraph: true;">end</span> <span style="-en-paragraph: true;">即对应数组后方插入一个非常大的数，那么要插入的数就一定在</span><span style="-en-paragraph: true;">start</span> <span style="-en-paragraph: true;">和</span><span style="-en-paragraph: true;">end</span> <span style="-en-paragraph: true;">之间了。</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">有时复杂的边界条件处理可以通过『补项』这种优雅的方式巧妙处理。</span></div><h3>复杂度分析</h3><div><span style="-en-paragraph: true;">时间复杂度</span> <span style="-en-paragraph: true;">O(logn)O(\log n)</span><span style="-en-paragraph: true;">O</span><span style="-en-paragraph: true;">(</span><span style="-en-paragraph: true;">lo</span><span style="-en-paragraph: true;">g</span><span style="-en-paragraph: true;">n</span><span style="-en-paragraph: true;">)</span><span style="-en-paragraph: true;">, 空间复杂度</span> <span style="-en-paragraph: true;">O(1)O(1)</span><span style="-en-paragraph: true;">O</span><span style="-en-paragraph: true;">(</span><span style="-en-paragraph: true;">1</span><span style="-en-paragraph: true;">)</span><span style="-en-paragraph: true;">.</span></div><div><br/></div><h1>Search for a Range</h1><div><span style="-en-paragraph: true;">Given a sorted array of</span> <span style="-en-paragraph: true; font-style: italic;">n</span> <span style="-en-paragraph: true;">integers, find the starting and ending position of</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">a given target value.</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">If the target is not found in the array, return</span> <span style="-en-paragraph: true;">[-1, -1]</span><span style="-en-paragraph: true;">.</span></div><h4>Example</h4><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">Given</span> <span style="-en-paragraph: true;">[5, 7, 7, 8, 8, 10]</span> <span style="-en-paragraph: true;">and target value</span> <span style="-en-paragraph: true;">8</span><span style="-en-paragraph: true;">, return</span> <span style="-en-paragraph: true;">[3, 4]</span><span style="-en-paragraph: true;">.</span></div><h4>Challenge</h4><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">O(log</span> <span style="-en-paragraph: true; font-style: italic;">n</span><span style="-en-paragraph: true;">) time.</span></div><h2>题解</h2><h3>Python</h3><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">first/last position 结合。</span></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class Solution:</div><div>    &quot;&quot;&quot;</div><div>    @param A : a list of integers</div><div>    @param target : an integer to be searched</div><div>    @return : a list of length 2, [index1, index2]</div><div>    &quot;&quot;&quot;</div><div>    def searchRange(self, A, target):</div><div>        ret = [-1, -1]</div><div>        if not A:</div><div>            return ret</div><div><br/></div><div>        # find the first position of target</div><div>        <b><font color="#FF0000">st, ed = 0, len(A) - 1    //二分法核心</font></b></div><div><b><font color="#FF0000">        while st + 1 &lt; ed:</font></b></div><div><b><font color="#FF0000">            mid = (st + ed) / 2</font></b></div><div><b><font color="#FF0000">            if A[mid] == target:</font></b></div><div><b><font color="#FF0000">                ed = mid</font></b></div><div><b><font color="#FF0000">            elif A[mid] &lt; target:</font></b></div><div><b><font color="#FF0000">                st = mid</font></b></div><div><b><font color="#FF0000">            else:</font></b></div><div><b><font color="#FF0000">                ed = mid</font></b></div><div>        if A[st] == target:</div><div>            ret[0] = st</div><div>        elif A[ed] == target:</div><div>            ret[0] = ed</div><div>        # find the last position of target</div><div>        st, ed = 0, len(A) - 1</div><div>        while st + 1 &lt; ed:</div><div>            mid = (st + ed) / 2</div><div>            if A[mid] == target:</div><div>                st = mid</div><div>            elif A[mid] &lt; target:</div><div>                st = mid</div><div>            else:</div><div>                ed = mid</div><div>        if A[ed] == target:</div><div>            ret[1] = ed</div><div>        elif A[st] == target:</div><div>            ret[1] = st</div><div><br/></div><div>        return ret</div></div><div><br/></div><h1>Search a 2D Matrix</h1><h3>Problem Statement</h3><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">Write an efficient algorithm that searches for a value in an</span> <span style="-en-paragraph: true; font-style: italic;">m</span> <span style="-en-paragraph: true;">x</span> <span style="-en-paragraph: true; font-style: italic;">n</span> <span style="-en-paragraph: true;">matrix.</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">This matrix has the following properties:</span></div><ul><li>Integers in each row are sorted from left to right.</li><li>The first integer of each row is greater than the last integer of the previous row.</li></ul><h4>Example</h4><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">Consider the following matrix:</span></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>[</div><div>    [1, 3, 5, 7],</div><div>    [10, 11, 16, 20],</div><div>    [23, 30, 34, 50]</div><div>]</div></div><div><br/></div><div><br/></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">Given</span> <span style="-en-paragraph: true;">target = 3</span><span style="-en-paragraph: true;">, return</span> <span style="-en-paragraph: true;">true</span><span style="-en-paragraph: true;">.</span></div><h4>Challenge</h4><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">O(log(n) + log(m)) time</span></div><h2>题解 - 一次二分搜索 V.S. 两次二分搜索</h2><ul><li><span style="font-weight: bold;">一次二分搜索</span> - 由于矩阵按升序排列，因此可将二维矩阵转换为一维问题。对原始的二分搜索进行适当改变即可(求行和列)。时间复杂度为 O(log(mn))=O(log(m)+log(n))O(log(mn))=O(log(m)+log(n))O(log(mn))=O(log(m)+log(n))</li><li><span style="font-weight: bold;">两次二分搜索</span> - 先按行再按列进行搜索，即两次二分搜索。时间复杂度相同。</li></ul><h2>一次二分搜索</h2><h3>Python</h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class Solution:</div><div>    def search_matrix(self, matrix, target):</div><div>        # Find the first position of target</div><div>        if not matrix or not matrix[0]:</div><div>            return False</div><div>        m, n = len(matrix), len(matrix[0])</div><div>        st, ed = 0, m * n - 1</div><div><br/></div><div>        <b><font color="#E30000">while st + 1 &lt; ed:</font></b></div><div><b><font color="#E30000">            mid = (st + ed) / 2</font></b></div><div><b><font color="#E30000">            if matrix[mid / n][mid % n] == target:</font></b></div><div><b><font color="#E30000">                return True</font></b></div><div><b><font color="#E30000">            elif matrix[mid / n][mid % n] &lt; target:</font></b></div><div><b><font color="#E30000">                st = mid</font></b></div><div><b><font color="#E30000">            else:</font></b></div><div><b><font color="#E30000">                ed = mid</font></b></div><div>        return matrix[st / n][st % n] == target or \</div><div>                matrix[ed / n][ed % n] == target</div></div><h2>两次二分法</h2><h3>Python</h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class Solution:</div><div>    def search_matrix(self, matrix, target):</div><div>        if not matrix or not matrix[0]:</div><div>            return False</div><div><br/></div><div>        # first pos &gt;= target</div><div>        st, ed = 0, len(matrix) - 1</div><div>        while st + 1 &lt; ed:</div><div>            mid = (st + ed) / 2</div><div>            if matrix[mid][-1] == target:</div><div>                st = mid</div><div>            elif matrix[mid][-1] &lt; target:</div><div>                st = mid</div><div>            else:</div><div>                ed = mid</div><div>        if matrix[st][-1] &gt;= target:</div><div>            row = matrix[st]</div><div>        elif matrix[ed][-1] &gt;= target:</div><div>            row = matrix[ed]</div><div>        else:</div><div>            return False</div><div><br/></div><div>        # binary search in row</div><div>        st, ed = 0, len(row) - 1</div><div>        while st + 1 &lt; ed:</div><div>            mid = (st + ed) / 2</div><div>            if row[mid] == target:</div><div>                return True</div><div>            elif row[mid] &lt; target:</div><div>                st = mid</div><div>            else:</div><div>                ed = mid</div><div>        return row[st] == target or row[ed] == target</div></div><div><br/></div><div><br/></div><h1>Math and Bit Manipulation</h1><h1><span style="font-weight: bold; font-size: 20pt;">- 数学和位运算（一）</span></h1></div><h2><span style="font-weight: bold;">Question</span></h2><ul><li>lintcode: <a href="http://www.lintcode.com/en/problem/single-number/">(82) Single Number</a></li></ul><div><span style="font-weight: bold;">Given 2*n + 1 numbers, every numbers occurs twice except one, find it.</span></div><div><br style="font-weight: bold;"/></div><div><span style="font-weight: bold;">Example</span></div><div><span style="font-weight: bold;">Given [1,2,2,1,3,4,3], return 4</span></div><div><br style="font-weight: bold;"/></div><div><span style="font-weight: bold;">Challenge</span></div><div><span style="font-weight: bold;">One-pass, constant extra space</span></div><h2><span style="font-weight: bold;">题解</span></h2><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true; font-weight: bold;">根据题意，共有</span><span style="-en-paragraph: true; font-weight: bold;">2*n + 1</span><span style="-en-paragraph: true; font-weight: bold;">个数，且有且仅有一个数落单，要找出相应的「单数」。鉴于有空间复杂度的要求，不可能使用另外一个数组来保存每个数出现的次数，考虑到异或运算的特性，根据</span><span style="-en-paragraph: true; font-weight: bold;">x ^ x = 0</span><span style="-en-paragraph: true; font-weight: bold;">和</span><span style="-en-paragraph: true; font-weight: bold;">x ^ 0 = x</span><span style="-en-paragraph: true; font-weight: bold;">可将给定数组的所有数依次异或，最后保留的即为结果。</span></div><h3><span style="font-weight: bold;">C++</span></h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div><span style="font-weight: bold;">class Solution {</span></div><div><span style="font-weight: bold;">public:</span></div><div><span style="font-weight: bold;">    /**</span></div><div><span style="font-weight: bold;">     * @param A: Array of integers.</span></div><div><span style="font-weight: bold;">     * return: The single number.</span></div><div><span style="font-weight: bold;">     */</span></div><div><span style="font-weight: bold;">    int singleNumber(vector&lt;int&gt; &amp;A) {</span></div><div><span style="font-weight: bold;">        if (A.empty()) {</span></div><div><span style="font-weight: bold;">            return -1;</span></div><div><span style="font-weight: bold;">        }</span></div><div><span style="font-weight: bold;">        int result = 0;</span></div><div><br style="font-weight: bold;"/></div><div><span style="font-weight: bold;">        for (vector&lt;int&gt;::iterator iter = A.begin(); iter != A.end(); ++iter) {</span></div><div><span style="font-weight: bold;">            result = result ^ *iter;</span></div><div><span style="font-weight: bold;">        }</span></div><div><br style="font-weight: bold;"/></div><div><span style="font-weight: bold;">        return result;</span></div><div><span style="font-weight: bold;">    }</span></div></div><div><span style="font-weight: bold;">};</span></div><h3><span style="font-weight: bold;">源码分析</span></h3><ol><li>异常处理(OJ上对于空vector的期望结果为0，但个人认为-1更为合理)</li><li>初始化返回结果result为0，因为x ^ 0 = x</li></ol><div><br/></div><h1>Single Number II</h1><h2>Question</h2><ul><li>leetcode: <a href="https://leetcode.com/problems/single-number-ii/">Single Number II | LeetCode OJ</a></li><li>lintcode: <a href="http://www.lintcode.com/en/problem/single-number-ii/">(83) Single Number II</a></li></ul><h3>Problem Statement</h3><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">Given</span> <span style="-en-paragraph: true;">3*n + 1</span> <span style="-en-paragraph: true;">numbers, every numbers occurs triple times except one, find</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">it.</span></div><h4>Example</h4><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">Given</span> <span style="-en-paragraph: true;">[1,1,2,3,3,3,2,2,4,1]</span> <span style="-en-paragraph: true;">return</span> <span style="-en-paragraph: true;">4</span></div><h4>Challenge</h4><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">One-pass, constant extra space.</span></div><h2>题解1 - 逐位处理</h2><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">上题 Single Number 用到了二进制中异或的运算特性，这题给出的元素数目为</span><span style="-en-paragraph: true;">3*n + 1</span><span style="-en-paragraph: true;">，因此我们很自然地想到如果有种运算能满足「三三运算」为0该有多好！对于三个相同的数来说，其相加的和必然是3的倍数，仅仅使用这一个特性还不足以将单数找出来，我们再来挖掘隐含的信息。以3为例，若使用不进位加法，三个3相加的结果为：</span></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>0011</div><div>0011</div><div>0011</div><div>----</div><div>0033</div></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">注意到其中的奥义了么？三个相同的数相加，不仅其和能被3整除，其二进制位上的每一位也能被3整除！因此我们只需要一个和</span><span style="-en-paragraph: true;">int</span><span style="-en-paragraph: true;">类型相同大小的数组记录每一位累加的结果即可。时间复杂度约为</span> <span style="-en-paragraph: true;">O((3n+1)⋅sizeof(int)⋅8)O((3n+1)\cdot sizeof(int) \cdot 8)</span><span style="-en-paragraph: true;">O</span><span style="-en-paragraph: true;">(</span><span style="-en-paragraph: true;">(</span><span style="-en-paragraph: true;">3</span><span style="-en-paragraph: true;">n</span><span style="-en-paragraph: true;">+</span><span style="-en-paragraph: true;">1</span><span style="-en-paragraph: true;">)</span><span style="-en-paragraph: true;">⋅</span><span style="-en-paragraph: true;">s</span><span style="-en-paragraph: true;">i</span><span style="-en-paragraph: true;">z</span><span style="-en-paragraph: true;">e</span><span style="-en-paragraph: true;">o</span><span style="-en-paragraph: true;">f</span><span style="-en-paragraph: true;">(</span><span style="-en-paragraph: true;">i</span><span style="-en-paragraph: true;">n</span><span style="-en-paragraph: true;">t</span><span style="-en-paragraph: true;">)</span><span style="-en-paragraph: true;">⋅</span><span style="-en-paragraph: true;">8</span><span style="-en-paragraph: true;">)</span></div><h3>Python</h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class Solution(object):</div><div>    def singleNumber(self, nums):</div><div>        &quot;&quot;&quot;</div><div>        :type nums: List[int]</div><div>        :rtype: int</div><div>        &quot;&quot;&quot;</div><div>        if nums is None:</div><div>            return 0</div><div><br/></div><div>        result = 0</div><div>        for i in xrange(32):</div><div>            bit_i_sum = 0</div><div>            for num in nums:</div><div>                bit_i_sum += ((num &gt;&gt; i) &amp; 1)</div><div>            result |= ((bit_i_sum % 3) &lt;&lt; i)</div><div>        return self.twos_comp(result, 32)</div><div><br/></div><div>    def twos_comp(self, val, bits):</div><div>        &quot;&quot;&quot;</div><div>        compute the 2's compliment of int value val</div><div>        e.g. -4 ==&gt; 11100 == -(10000) + 01100</div><div>        &quot;&quot;&quot;</div><div>        return -(val &amp; (1 &lt;&lt; (bits - 1))) | (val &amp; ((1 &lt;&lt; (bits - 1)) - 1))</div></div><h1>Single Number III</h1><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">Given 2*n + 2 numbers, every numbers occurs twice except two, find them.</span></div><div><br style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"/></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">Example</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">Given [1,2,2,3,4,4,5,3] return 1 and 5</span></div><div><br style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"/></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">Challenge</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">O(n) time, O(1) extra space.</span></div></div><h1>O(1) Check Power of 2</h1><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">Using O(1) time to check whether an integer n is a power of 2.</span></div><div><br style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"/></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">Example</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">For n=4, return true;</span></div><div><br style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"/></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">For n=5, return false;</span></div><div><br style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"/></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">Challenge</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">O(1) time</span></div></div><div>简单点来考虑可以连除2求余，看最后的余数是否为1，但是这种方法无法在 O(1)O(1)O(1) 的时间内解出，所以我们必须要想点别的办法了。2的整数幂若用二进制来表示，则其中必只有一个1，其余全是0，那么怎么才能用一个式子把这种特殊的关系表示出来了？传统的位运算如按位与、按位或和按位异或等均无法直接求解，我就不卖关子了，<font style="color: rgb(227, 0, 0);"><b>比较下</b><b><span style="-en-paragraph: true;">x - 1</span><span style="-en-paragraph: true;">和</span><span style="-en-paragraph: true;">x</span><span style="-en-paragraph: true;">的关系试试？以</span><span style="-en-paragraph: true;">x=4</span></b><b>为例</b></font>。</div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>0100 ==&gt; 4</div><div>0011 ==&gt; 3</div></div><div><span style="-en-paragraph: true;">两个数进行按位与就为0了！如果不是2的整数幂则无上述关系，反证法可证之。</span></div><div><br/></div><h1>Convert Integer A to Integer B</h1><div><br/></div><div><br/></div><div><br/></div><div><br/></div><h1>Factorial Trailing Zeroes</h1><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>Write an algorithm which computes the number of trailing zeros in n factorial.</div><div><br/></div><div>Example</div><div>11! = 39916800, so the out should be 2</div><div><br/></div><div>Challenge</div><div>O(log N) time</div></div><div><span style="-en-paragraph: true;">找阶乘数中末尾的连零数量，容易想到的是找相乘能为10的整数倍的数，如</span> <span style="-en-paragraph: true;">2×52 \times 5</span><span style="-en-paragraph: true;">2</span><span style="-en-paragraph: true;">×</span><span style="-en-paragraph: true;">5</span><span style="-en-paragraph: true;">,</span> <span style="-en-paragraph: true;">1×101 \times 10</span><span style="-en-paragraph: true;">1</span><span style="-en-paragraph: true;">×</span><span style="-en-paragraph: true;">1</span><span style="-en-paragraph: true;">0</span> <span style="-en-paragraph: true;">等，遥想当初做阿里笔试题时遇到过类似的题，当时想着算算5和10的个数就好了，可万万没想到啊，25可以变为两个5相乘！真是蠢死了... 根据数论里面的知识，任何正整数都可以表示为它的质因数的乘积[^wikipedia]。所以比较准确的思路应该是计算质因数5和2的个数，取小的即可。质因数2的个数显然要大于5的个数，故只需要计算给定阶乘数中质因数中5的个数即可。原题的问题即转化为求阶乘数中质因数5的个数，首先可以试着分析下100以内的数，再试试100以上的数，聪明的你一定想到了可以使用求余求模等方法 :)</span></div><h3>Python</h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class Solution:</div><div>    # @param {integer} n</div><div>    # @return {integer}</div><div>    def trailingZeroes(self, n):</div><div>        if n &lt; 0:</div><div>            return -1</div><div><br/></div><div>        count = 0</div><div>        while n &gt; 0:</div><div>            n /= 5</div><div>            count += n</div><div><br/></div><div>        return count</div></div><div><br/></div><h2>题解2 - Recursive</h2><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><b><font style="color: rgb(173, 0, 0);">可以使用迭代处理的程序往往用递归，而且往往更为优雅。</font></b>递归的终止条件为n &lt;= 0.</div><h3>Python</h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class Solution:</div><div>    # @param {integer} n</div><div>    # @return {integer}</div><div>    def trailingZeroes(self, n):</div><div>        if n == 0:</div><div>            return 0</div><div>        elif n &lt; 0:</div><div>            return -1</div><div>        else:</div><div>            return n / 5 + self.trailingZeroes(n / 5)</div></div><div><br/></div><div><br/></div><div><br/></div><h1>Unique Binary Search Trees</h1><div>Given n, how many structurally unique BSTs (binary search trees)</div><div>that store values 1...n?</div><div><br/></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>Example</div><div>Given n = 3, there are a total of 5 unique BST's.</div><div><span style="line-height: 1.45;">1          3    3       2      1</span><br/></div><div>\         /    /       / \      \</div><div> 3      2     1       1   3      2</div><div>/      /       \                  \</div><div>2     1         2                  3</div></div><div><h2>题解1 - 两重循环</h2><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">挺有意思的一道题，与数据结构和动态规划都有点关系。这两天在骑车路上和睡前都一直在想，始终未能找到非常明朗的突破口，直到看到这么一句话——『以i为根节点的树，其左子树由[0, i-1]构成， 其右子树由[i+1, n]构成。』这不就是 BST 的定义嘛！灵活运用下就能找到递推关系了。</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">容易想到这道题的动态规划状态为 count[n], count[n] 表示到正整数 i 为止的二叉搜索树个数。容易得到 count[1] = 1, 根节点为1，count[2] = 2, 根节点可为1或者2。那么 count[3] 的根节点自然可为1，2，3. 如果以1为根节点，那么根据 BST 的定义，2和3只可能位于根节点1的右边；如果以2为根节点，则1位于左子树，3位于右子树；如果以3为根节点，则1和2必位于3的左子树。</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">抽象一下，如果以 i 作为根节点，由基本的排列组合知识可知，其唯一 BST 个数为左子树的 BST 个数乘上右子树的 BST 个数。故对于 i 来说，其左子树由[0, i - 1]构成，唯一的 BST 个数为 count[i - 1], 右子树由[i + 1, n] 构成，其唯一的 BST 个数没有左子树直观，但是也有迹可循。对于两组有序数列「1, 2, 3] 和 [4, 5, 6]来说，</span><span style="-en-paragraph: true; font-weight: bold;">这两个有序数列分别组成的 BST 个数必然是一样的，因为 BST 的个数只与有序序列的大小有关，而与具体值没有关系。</span><span style="-en-paragraph: true;">所以右子树的 BST 个数为 count[n - i]，于是乎就得到了如下递推关系：</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><img src="DSASolution_files/Image.png" type="image/png" data-filename="Image.png"/><br/></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">网上有很多用 count[3] 的例子来得到递推关系，恕本人愚笨，在没有从 BST 的定义和有序序列个数与 BST 关系分析的基础上，我是不敢轻易说就能得到如上状态转移关系的。</span></div><h3>Python</h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class Solution:</div><div>    # @paramn n: An integer</div><div>    # @return: An integer</div><div>    def numTrees(self, n):</div><div>        if n &lt; 0:</div><div>            return -1</div><div><br/></div><div>        count = [0] * (n + 1)</div><div>        count[0] = 1</div><div>        for i in xrange(1, n + 1):</div><div>            for j in xrange(i):</div><div>                count[i] += count[j] * count[i - j - 1]</div><div><br/></div><div>        return count[n]</div></div></div><div><br/></div><h1>Update Bits</h1><div><br/></div><div><br/></div><div><br/></div><h1>Hash Function</h1><h2>Question</h2><h2>Question</h2><ul><li>lintcode: <a href="http://www.lintcode.com/en/problem/hash-function/">(128) Hash Function</a></li></ul><h3>Problem Statement</h3><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">In data structure Hash, hash function is used to convert a string(or any other</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">type) into an integer smaller than hash size and bigger or equal to zero. The</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">objective of designing a hash function is to &quot;hash&quot; the key as unreasonable as</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">possible. A good hash function can avoid collision as less as possible. A</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">widely used hash function algorithm is using a magic number 33, consider any</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">string as a 33 based big integer like follow:</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">hashcode(&quot;abcd&quot;) = (ascii(a)</span> <span style="-en-paragraph: true; font-style: italic;">33333^3</span><span style="-en-paragraph: true; font-style: italic;">3</span><span style="-en-paragraph: true; font-style: italic;">3</span><span style="-en-paragraph: true; font-style: italic; top: -0.363em;">3</span> <span style="-en-paragraph: true; font-style: italic;">+ ascii(b)</span> <span style="-en-paragraph: true;">33233^2</span><span style="-en-paragraph: true;">3</span><span style="-en-paragraph: true;">3</span><span style="-en-paragraph: true; top: -0.363em;">2</span> <span style="-en-paragraph: true;">+ ascii(c) *33 +</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">ascii(d)) % HASH_SIZE</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">= (97</span> <span style="-en-paragraph: true; font-style: italic;">33333^3</span><span style="-en-paragraph: true; font-style: italic;">3</span><span style="-en-paragraph: true; font-style: italic;">3</span><span style="-en-paragraph: true; font-style: italic; top: -0.363em;">3</span> <span style="-en-paragraph: true; font-style: italic;">+ 98</span> <span style="-en-paragraph: true;">33233^2</span><span style="-en-paragraph: true;">3</span><span style="-en-paragraph: true;">3</span><span style="-en-paragraph: true; top: -0.363em;">2</span> <span style="-en-paragraph: true;">+ 99 * 33 +100) % HASH_SIZE</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">= 3595978 % HASH_SIZE</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">here HASH_SIZE is the capacity of the hash table (you can assume a hash table</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">is like an array with index 0 ~ HASH_SIZE-1).</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">Given a string as a key and the size of hash table, return the hash value of</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">this key.f</span></div><h4>Example</h4><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">For key=&quot;abcd&quot; and size=100, return 78</span></div><h4>Clarification</h4><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">For this problem, you are not necessary to design your own hash algorithm or</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">consider any collision issue, you just need to implement the algorithm as</span></div><div><span style="-en-paragraph: true;">described.</span></div><h2>题解1</h2><div>基本实现题，大多数人看到题目的直觉是按照定义来递推不就得了嘛，但其实这里面大有玄机，因为在字符串较长时使用 long 型来计算33的幂会溢出！所以这道题的关键在于如何处理<span style="-en-paragraph: true; font-weight: bold;">大整数溢出</span>。<font style="color: rgb(173, 0, 0);"><b>对于整数求模，</b><b>(a * b) % m = a % m * b % m</b> <b>这个基本公式务必牢记。</b></font>根据这个公式我们可以大大降低时间复杂度和规避溢出。</div><div><br/></div><div><br/></div><h1>Count 1 in Binary</h1><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>Count how many 1 in binary representation of a 32-bit integer.</div><div><br/></div><div>Example</div><div>Given 32, return 1</div><div><br/></div><div>Given 5, return 2</div><div><br/></div><div>Given 1023, return 9</div><div><br/></div><div>Challenge</div><div>If the integer is n bits with m 1 bits. Can you do it in O(m) time?</div></div><div><span style="-en-paragraph: true;">题</span> <a href="http://algorithm.yuanbin.me/zh-hans/math_and_bit_manipulation/o1_check_power_of_2.html" style="-en-paragraph: true;">O1 Check Power of 2</a> <span style="-en-paragraph: true;">的进阶版，</span><b><font style="color: rgb(173, 0, 0); background-color: rgb(255, 250, 165);-evernote-highlight:true;"><u><span style="-en-paragraph: true;">x &amp; (x - 1)</span> <span style="-en-paragraph: true;">的含义为去掉二进制数中1的最后一位，无论 x 是正数还是负数都成立。</span></u></font></b></div><h3>C++</h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class Solution {</div><div>public:</div><div>    /**</div><div>     * @param num: an integer</div><div>     * @return: an integer, the number of ones in num</div><div>     */</div><div>    int countOnes(int num) {</div><div>        int count=0;</div><div>        while (num) {</div><div>            num &amp;= num-1;</div><div>            count++;</div><div>        }</div><div>        return count;</div><div>    }</div><div>};</div></div><div><br/></div><h1>Fibonacci</h1><h2>题解</h2><div><span style="-en-paragraph: true;">斐波那契数列使用递归极其容易实现，其实使用非递归的方法也很容易，不断向前滚动即可。</span></div><h3>C++</h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class Solution{</div><div>public:</div><div>    /**</div><div>     * @param n: an integer</div><div>     * @return an integer f(n)</div><div>     */</div><div>    int fibonacci(int n) {</div><div>        if (n &lt;= 0) return -1;</div><div>        if (n == 1) return 0;</div><div>        if (n == 2) return 1;</div><div><br/></div><div>        int fn = 0, fn1 = 0, fn2 = 1;</div><div>        for (int i = 3; i &lt;= n; i++) {</div><div>            fn = fn1 + fn2;</div><div>            fn1 = fn2;</div><div>            fn2 = fn;</div><div>        }</div><div>        return fn;</div><div>    }</div><div>};</div></div><h1>A plus B Problem</h1><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>Write a function that add two numbers A and B.</div><div>You should not use + or any arithmetic operators.</div><div><br/></div><div><br/></div><div>Example</div><div>Given a=1 and b=2 return 3</div></div><div><br/></div><h2>题解</h2><div><span style="-en-paragraph: true;">不用加减法实现加法，类似数字电路中的全加器，异或求得部分和，相与求得进位，最后将进位作为加法器的输入，典型的递归实现思路。</span></div><h3>Java</h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class Solution {</div><div>    /*</div><div>     * param a: The first integer</div><div>     * param b: The second integer</div><div>     * return: The sum of a and b</div><div>     */</div><div>    public int aplusb(int a, int b) {</div><div>        int result = a ^ b;</div><div>        int carry = a &amp; b;</div><div>        carry &lt;&lt;= 1;</div><div>        if (carry != 0) {</div><div>            result = aplusb(result, carry);</div><div>        }</div><div><br/></div><div>        return result;</div><div>    }</div><div>}</div></div><h1>Print Numbers by Recursion</h1><h2>题解</h2><div><span style="-en-paragraph: true;">从小至大打印 N 位的数列，正如题目中所提供的</span> <span style="-en-paragraph: true;">recursion(i)</span><span style="-en-paragraph: true;">, 解法简单粗暴，但问题在于 N 稍微大一点时栈就溢出了，因为递归深度太深了。能联想到的方法大概有两种，一种是用排列组合的思想去解释，把0~9当成十个不同的数(字符串表示)，塞到 N 个坑位中，这个用 DFS 来解应该是可行的；另一个则是使用数学方法，依次递归递推，比如 N=2 可由 N=1递归而来，具体方法则是乘10进位加法。题中明确要求递归深度最大不超过 N, 故 DFS 方法比较危险。</span></div><div><span style="-en-paragraph: true;"><br/></span></div><div><span style="-en-paragraph: true;"><br/></span></div><div><span style="-en-paragraph: true;"><br/></span></div><div><span style="-en-paragraph: true;"><br/></span></div><div><span style="-en-paragraph: true;"><br/></span></div><div><span style="-en-paragraph: true;"><br/></span></div><h1>Majority Number</h1><h2><span style="font-weight: bold; font-size: 11pt;">题解</span></h2><h3><span style="-en-paragraph: true; font-weight: bold; font-size: 11pt;">找出现次数超过一半的数，使用哈希表统计不同数字出现的次数，超过二分之一即返回当前数字。这种方法非常简单且容易实现，但会占据过多空间，注意到题中明确表明要找的数会超过二分之一，这里的隐含条件不是那么容易应用。既然某个数超过二分之一，那么用这个数和其他数进行 PK，不同的计数器都减一</span><span style="-en-paragraph: true; font-weight: bold; font-size: 11pt;">（核心在于两两抵消）</span><span style="-en-paragraph: true; font-weight: bold; font-size: 11pt;">，相同的则加1，最后返回计数器大于0的即可。综上，我们需要一辅助数据结构如</span><span style="-en-paragraph: true; font-weight: bold; font-size: 11pt;">pair&lt;int, int&gt;</span><span style="-en-paragraph: true; font-weight: bold; font-size: 11pt;">.</span></h3><h3>C++</h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>int majorityNumber(vector&lt;int&gt; nums) {</div><div>    if (nums.empty()) return -1;</div><div><br/></div><div>    int k = -1, count = 0;</div><div>    for (auto n : nums) {</div><div>        if (!count) k = n;</div><div>        if (k == n) count++;</div><div>        else count--;</div><div>    }</div><div>    return k;</div><div>}</div><div><br/></div><div><br/></div><div><br/></div></div><div><span style="-en-paragraph: true;"><br/></span></div><div><span style="-en-paragraph: true;"><br/></span></div><h1>Majority Number II</h1><h2>题解</h2><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">题</span> <a href="http://algorithm.yuanbin.me/zh-hans/math_and_bit_manipulation/majority_number.html" style="-en-paragraph: true;">Majority Number</a> <span style="-en-paragraph: true;">的升级版，之前那道题是『两两抵消』，这道题自然则需要『三三抵消』，不过『三三抵消』需要注意不少细节，比如两个不同数的添加顺序和添加条件。</span></div><h3>C++</h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class Solution {</div><div>public:</div><div>    /**</div><div>     * @param nums: A list of integers</div><div>     * @return: The majority number occurs more than 1/3.</div><div>     */</div><div>    int majorityNumber(vector&lt;int&gt; nums) {</div><div>        if (nums.empty()) return -1;</div><div><br/></div><div>        int k1 = 0, k2 = 0, c1 = 0, c2 = 0;</div><div>        for (auto n : nums) {</div><div>            if (!c1 || k1 == n) {</div><div>                k1 = n;</div><div>                c1++;</div><div>            } else if (!c2 || k2 == n) {</div><div>                k2 = n;</div><div>                c2++;</div><div>            } else {</div><div>                c1--;</div><div>                c2--;</div><div>            }</div><div>        }</div><div><br/></div><div>        c1 = 0;</div><div>        c2 = 0;</div><div>        for (auto n : nums) {</div><div>            if (n == k1) c1++;</div><div>            if (n == k2) c2++;</div><div>        }</div><div>        return c1 &gt; c2 ? k1 : k2;</div><div>    }</div><div>};</div></div><div><span style="-en-paragraph: true;"><br/></span></div><h1>Majority Number III</h1><h2>题解</h2><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><a href="http://algorithm.yuanbin.me/zh-hans/math_and_bit_manipulation/majority_number_ii.html" style="-en-paragraph: true;">Majority Number II</a> <span style="-en-paragraph: true;">的升级版，有了前两道题的铺垫，此题的思路已十分明了，对 K-1个数进行相互抵消，这里不太可能使用 key1, key2...等变量，用数组使用上不太方便，且增删效率不高，故使用哈希表较为合适，当哈希表的键值数等于 K 时即进行清理，当然更准备地来讲应该是等于 K-1时清理。故此题的逻辑即为：1. 更新哈希表，若遇哈希表 size == K 时则执行删除操作，最后遍历哈希表取真实计数器值，返回最大的 key.</span></div><h3>C++</h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class Solution {</div><div>public:</div><div>    /**</div><div>     * @param nums: A list of integers</div><div>     * @param k: As described</div><div>     * @return: The majority number</div><div>     */</div><div>    int majorityNumber(vector&lt;int&gt; nums, int k) {</div><div>        unordered_map&lt;int, int&gt; map;</div><div><br/></div><div>        for (auto n : nums) {</div><div>           if (map.size() &lt; k) map[n]++;</div><div>           else {</div><div>                if (map.count(n)) map[n]++;</div><div>                else {</div><div>                    map[n] = 1;</div><div>                    vector&lt;int&gt; keys;</div><div>                    for (auto &amp;it : map) {</div><div>                        it.second--;</div><div>                        if (!it.second) keys.push_back(it.first);</div><div>                    }</div><div>                    for (int i : keys) map.erase(i);</div><div>                }</div><div>            }   </div><div>        }</div><div><br/></div><div>        int mx = 0;</div><div>        int ret = 0;</div><div>        for (auto &amp;it : map) {</div><div>            if (it.second &gt; mx) {</div><div>                ret = it.first;</div><div>                mx = it.second;</div><div>            }</div><div>        }</div><div>        return ret;</div><div>    }</div><div>};</div></div><div><span style="-en-paragraph: true;"><br/></span></div><h1>Digit Counts</h1><h2>Question</h2><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>Count the number of k's between 0 and n. k can be 0 - 9.</div><div><br/></div><div>Example</div><div>if n=12, k=1 in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],</div><div>we have FIVE 1's (1, 10, 11, 12)</div></div><div><span style="-en-paragraph: true;"><br/></span></div><h2>题解</h2><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">leetcode 上的有点简单，这里以 Lintcode 上的为例进行说明。找出从0至整数 n 中出现数位k的个数，与整数有关的题大家可能比较容易想到求模求余等方法，但其实很多与整数有关的题使用字符串的解法更为便利。将整数 i 分解为字符串，然后遍历之，自增 k 出现的次数即可。</span></div><h3>C++</h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class Solution {</div><div>public:</div><div>    /*</div><div>     * param k : As description.</div><div>     * param n : As description.</div><div>     * return: How many k's between 0 and n.</div><div>     */</div><div>    int digitCounts(int k, int n) {</div><div>        char c = k + '0';</div><div>        int count = 0;</div><div>        for (int i = k; i &lt;= n; i++) {</div><div>            for (auto s : to_string(i)) {</div><div>                if (s == c) count++;</div><div>            }</div><div>        }</div><div>        return count;</div><div>    }</div><div>};</div></div><div><span style="-en-paragraph: true;"><br/></span></div><h1>Ugly Number</h1><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">Ugly number is a number that only have factors 3, 5 and 7.</span></div><div><br style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"/></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">Design an algorithm to find the Kth ugly number.</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">The first 5 ugly numbers are 3, 5, 7, 9, 15 ...</span></div><div><br style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"/></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">Example</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">If K=4, return 9.</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">Challenge</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">O(K log K) or O(K) time.</span></div></div><h2>题解1 - TLE</h2><div><span style="-en-paragraph: true;">Lintcode 和 Leetcode 中质数稍微有点区别，这里以 Lintcode 上的版本为例进行说明。寻找第 K 个丑数，丑数在这里的定义是仅能被3，5，7整除。简单粗暴的方法就是挨个检查正整数，数到第 K 个丑数时即停止。</span></div><h2>题解2 - 二分查找</h2><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">根据丑数的定义，它的质因数只含有3, 5, 7, 那么根据这一点其实可以知道后面的丑数一定可以从前面的丑数乘3,5,7得到。那么可不可以将其递推关系用数学公式表示出来呢？</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">我大概做了下尝试，首先根据丑数的定义可以写成</span> <span style="-en-paragraph: true;">Uk=3x3⋅5x5⋅7x7U_k = 3^{x_3} \cdot 5^{x_5} \cdot 7^{x_7}</span><span style="-en-paragraph: true;">U</span><span style="-en-paragraph: true; top: 0.15em;">k</span><span style="-en-paragraph: true;">=</span><span style="-en-paragraph: true;">3</span><span style="-en-paragraph: true; top: -0.363em;">x</span><span style="-en-paragraph: true; top: 0.143em;">3</span><span style="-en-paragraph: true;">⋅</span><span style="-en-paragraph: true;">5</span><span style="-en-paragraph: true; top: -0.363em;">x</span><span style="-en-paragraph: true; top: 0.143em;">5</span><span style="-en-paragraph: true;">⋅</span><span style="-en-paragraph: true;">7</span><span style="-en-paragraph: true; top: -0.363em;">x</span><span style="-en-paragraph: true; top: 0.143em;">7</span><span style="-en-paragraph: true;">, 那么</span> <span style="-en-paragraph: true;">Uk+1U_{k+1}</span><span style="-en-paragraph: true;">U</span><span style="-en-paragraph: true; top: 0.15em;">k</span><span style="-en-paragraph: true; top: 0.15em;">+</span><span style="-en-paragraph: true; top: 0.15em;">1</span> <span style="-en-paragraph: true;">和</span> <span style="-en-paragraph: true;">UkU_k</span><span style="-en-paragraph: true;">U</span><span style="-en-paragraph: true; top: 0.15em;">k</span> <span style="-en-paragraph: true;">的不同则在于</span> <span style="-en-paragraph: true;">x3,x5,x7x_3, x_5, x_7</span><span style="-en-paragraph: true;">x</span><span style="-en-paragraph: true; top: 0.15em;">3</span><span style="-en-paragraph: true;">,</span><span style="-en-paragraph: true;">x</span><span style="-en-paragraph: true; top: 0.15em;">5</span><span style="-en-paragraph: true;">,</span><span style="-en-paragraph: true;">x</span><span style="-en-paragraph: true; top: 0.15em;">7</span> <span style="-en-paragraph: true;">的不同，递推关系为</span> <span style="-en-paragraph: true;">Uk+1=Uk⋅3y3⋅5y5⋅7y73z3⋅5z5⋅7z7U_{k+1} = U_k \cdot \frac{3^{y_3} \cdot 5^{y_5} \cdot 7^{y_7}}{3^{z_3} \cdot 5^{z_5} \cdot 7^{z_7}}</span><span style="-en-paragraph: true;">U</span><span style="-en-paragraph: true; top: 0.15em;">k</span><span style="-en-paragraph: true; top: 0.15em;">+</span><span style="-en-paragraph: true; top: 0.15em;">1</span><span style="-en-paragraph: true;">=</span><span style="-en-paragraph: true;">U</span><span style="-en-paragraph: true; top: 0.15em;">k</span><span style="-en-paragraph: true;">⋅</span><span style="-en-paragraph: true; top: 0.345em;">3</span><span style="-en-paragraph: true; top: -0.32177857142857147em;">z</span><span style="-en-paragraph: true; top: 0.29964em;">3</span><span style="-en-paragraph: true; top: 0.345em;">⋅</span><span style="-en-paragraph: true; top: 0.345em;">5</span><span style="-en-paragraph: true; top: -0.32177857142857147em;">z</span><span style="-en-paragraph: true; top: 0.29964em;">5</span><span style="-en-paragraph: true; top: 0.345em;">⋅</span><span style="-en-paragraph: true; top: 0.345em;">7</span><span style="-en-paragraph: true; top: -0.32177857142857147em;">z</span><span style="-en-paragraph: true; top: 0.29964em;">7</span><span style="-en-paragraph: true; top: -0.394em;">3</span><span style="-en-paragraph: true; top: -0.431em;">y</span><span style="-en-paragraph: true; top: 0.29964em;">3</span><span style="-en-paragraph: true; top: -0.394em;">⋅</span><span style="-en-paragraph: true; top: -0.394em;">5</span><span style="-en-paragraph: true; top: -0.431em;">y</span><span style="-en-paragraph: true; top: 0.29964em;">5</span><span style="-en-paragraph: true; top: -0.394em;">⋅</span><span style="-en-paragraph: true; top: -0.394em;">7</span><span style="-en-paragraph: true; top: -0.431em;">y</span><span style="-en-paragraph: true; top: 0.29964em;">7</span><span style="-en-paragraph: true;">,将这些分数按照从小到大的顺序排列可在 $$O(K)$$ 的时间内解决，但是问题来了，得到这些具体的</span> <span style="-en-paragraph: true;">y,zy, z</span><span style="-en-paragraph: true;">y</span><span style="-en-paragraph: true;">,</span><span style="-en-paragraph: true;">z</span> <span style="-en-paragraph: true;">就需要费不少时间，且人工操作极易漏解。:( 所以这种解法只具有数学意义，没有想到好的实现方法。</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">除了这种找相邻递推关系的方法我们还可以尝试对前面的丑数依次乘3, 5, 7，直至找到比当前最大的丑数大的一个数，对乘积后的三种不同结果取最小值即可得下一个最大的丑数。这种方法需要保存之前的 N 个丑数，由于已按顺序排好，天然的二分法。</span></div><h3>C++</h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class Solution {</div><div>public:</div><div>    /*</div><div>     * @param k: The number k.</div><div>     * @return: The kth prime number as description.</div><div>     */</div><div>    long long kthPrimeNumber(int k) {</div><div>        if (k &lt;= 0) return -1;</div><div><br/></div><div>        vector&lt;long long&gt; ugly(k + 1);</div><div>        ugly[0] = 1;</div><div>        int index = 0, index3 = 0, index5 = 0, index7 = 0;</div><div>        while (index &lt;= k) {</div><div>            long long val = ugly[index3]*3 &lt; ugly[index5]*5 ? ugly[index3]*3 : ugly[index5]*5;</div><div>            val = val &lt; ugly[index7]*7 ? val : ugly[index7]*7;</div><div>            if (val == ugly[index3]*3) ++index3;</div><div>            if (val == ugly[index5]*5) ++index5;</div><div>            if (val == ugly[index7]*7) ++index7;</div><div>            ugly[++index] = val;</div><div>        }</div><div>        return ugly[k];</div><div>    }</div><div>};</div></div><div><span style="-en-paragraph: true;"><br/></span></div><h2>题解3 - 动态规划</h2><div><span style="-en-paragraph: true;">TBD</span></div><div><span style="-en-paragraph: true;"><br/></span></div><h1>Plus One</h1><h4>Example</h4><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">Given [1,2,3] which represents 123, return [1,2,4].</span></div><div><span style="-en-paragraph: true;">Given [9,9,9] which represents 999, return [1,0,0,0].</span></div><div><span style="-en-paragraph: true;"><br/></span></div><h2>题解</h2><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">又是一道两个整数按数位相加的题，自后往前累加，处理下进位即可。这道题中是加1，其实还可以扩展至加2，加3等。</span></div><h3>C++</h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class Solution {</div><div>public:</div><div>    /**</div><div>     * @param digits a number represented as an array of digits</div><div>     * @return the result</div><div>     */</div><div>    vector&lt;int&gt; plusOne(vector&lt;int&gt;&amp; digits) {</div><div>        return plusN(digits, 1);</div><div>    }</div><div><br/></div><div>    vector&lt;int&gt; plusN(vector&lt;int&gt;&amp; digits, int n) {</div><div>        vector&lt;int&gt; result;</div><div>        int carry = n;</div><div>        for (int i = digits.size() - 1; i &gt;= 0; i--) {</div><div>            result.insert(result.begin(), (digits[i] + carry) % 10);</div><div>            carry = (digits[i] + carry) / 10;</div><div>        }</div><div>        if (carry) result.insert(result.begin(), carry);</div><div>        return result;</div><div>    }</div><div>};</div></div><div><span style="-en-paragraph: true;"><br/></span></div><div><span style="-en-paragraph: true;"><br/></span></div><div><span style="-en-paragraph: true;"><br/></span></div></div></span>
</div></body></html> 